import random
import time
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg, NavigationToolbar2Tk
import tkinter as tk
from tkinter import ttk, messagebox
import warnings

warnings.filterwarnings('ignore')
plt.rcParams['font.family'] = 'SimHei'
plt.rcParams['axes.unicode_minus'] = False

class NQueensMinConflicts:
    # 保持原有NQueensMinConflicts类不变
    def __init__(self, n):
        """初始化n皇后问题"""
        self.n = n
        # 每个索引代表一列，值代表该列皇后所在的行
        self.queens = list(range(n))  # 初始状态：每列一个皇后，放在不同行
        random.shuffle(self.queens)   # 随机打乱初始状态
    
    def count_conflicts(self, col, row):
        """计算将皇后放在指定位置时的冲突数"""
        conflicts = 0
        for c in range(self.n):
            if c == col:  # 跳过自身
                continue
            r = self.queens[c]
            # 检查是否在同一行
            if r == row:
                conflicts += 1
            # 检查是否在同一对角线
            if abs(c - col) == abs(r - row):
                conflicts += 1
        return conflicts
    
    def get_conflicts(self):
        """获取当前状态下所有皇后的冲突总数"""
        total_conflicts = 0
        for col in range(self.n):
            total_conflicts += self.count_conflicts(col, self.queens[col])
        # 由于每个冲突被计算了两次（两个皇后互相冲突），所以除以2
        return total_conflicts // 2
    
    def get_min_conflicts_position(self, col):
        """找到给定列中冲突最少的行位置"""
        min_conflicts = float('inf')
        min_positions = []
        
        for row in range(self.n):
            conflicts = self.count_conflicts(col, row)
            if conflicts < min_conflicts:
                min_conflicts = conflicts
                min_positions = [row]
            elif conflicts == min_conflicts:
                min_positions.append(row)
        
        # 如果有多个位置冲突相同，随机选择一个
        return random.choice(min_positions)
    
    def solve(self, max_steps=1000000):
        """使用最小冲突法求解n皇后问题"""
        steps = 0
        
        while steps < max_steps:
            # 计算当前的冲突总数
            conflicts = self.get_conflicts()
            if conflicts == 0:
                return True, steps  # 找到解决方案
            
            # 选择一个有冲突的皇后
            conflict_cols = []
            for col in range(self.n):
                if self.count_conflicts(col, self.queens[col]) > 0:
                    conflict_cols.append(col)
            
            if not conflict_cols:
                break  # 如果没有冲突的皇后但总冲突不为0，这是一个异常情况
            
            # 随机选择一个有冲突的列
            col = random.choice(conflict_cols)
            
            # 将该列的皇后移到冲突最少的位置
            self.queens[col] = self.get_min_conflicts_position(col)
            
            steps += 1
        
        return False, steps  # 达到最大步数未找到解决方案
    
    def verify_solution(self):
        """验证当前状态是否是有效解"""
        return self.get_conflicts() == 0

class NQueensUI:
    def __init__(self, root):
        self.root = root
        self.root.title("N皇后问题求解器")
        self.root.geometry("900x800")
        
        # 创建框架
        self.control_frame = ttk.Frame(root, padding="10")
        self.control_frame.pack(fill=tk.X)
        
        self.view_frame = ttk.Frame(root, padding="5")
        self.view_frame.pack(fill=tk.X)
        
        self.result_frame = ttk.Frame(root, padding="10")
        self.result_frame.pack(fill=tk.BOTH, expand=True)
        
        # 在控制框架中添加控件
        ttk.Label(self.control_frame, text="皇后数量(N):").pack(side=tk.LEFT, padx=5)
        
        self.n_var = tk.StringVar(value="200")
        self.n_entry = ttk.Entry(self.control_frame, textvariable=self.n_var, width=10)
        self.n_entry.pack(side=tk.LEFT, padx=5)
        
        self.start_button = ttk.Button(self.control_frame, text="开始求解", command=self.solve_queens)
        self.start_button.pack(side=tk.LEFT, padx=20)
        
        self.status_var = tk.StringVar(value="准备就绪")
        ttk.Label(self.control_frame, textvariable=self.status_var).pack(side=tk.LEFT, padx=10)
        
        # 添加局部视图控制
        ttk.Label(self.view_frame, text="局部视图开始位置:").pack(side=tk.LEFT, padx=5)
        self.view_start_var = tk.StringVar(value="0")
        self.view_start_entry = ttk.Entry(self.view_frame, textvariable=self.view_start_var, width=8)
        self.view_start_entry.pack(side=tk.LEFT, padx=5)
        
        ttk.Label(self.view_frame, text="显示大小:").pack(side=tk.LEFT, padx=5)
        self.view_size_var = tk.StringVar(value="50")
        self.view_size_entry = ttk.Entry(self.view_frame, textvariable=self.view_size_var, width=8)
        self.view_size_entry.pack(side=tk.LEFT, padx=5)
        
        self.update_view_button = ttk.Button(self.view_frame, text="更新视图", command=self.update_view)
        self.update_view_button.pack(side=tk.LEFT, padx=10)
        
        # 添加重置视图按钮
        self.reset_view_button = ttk.Button(self.view_frame, text="重置视图", command=self.reset_view)
        self.reset_view_button.pack(side=tk.LEFT, padx=10)
        
        # 创建结果显示区
        self.canvas_frame = ttk.Frame(self.result_frame)
        self.canvas_frame.pack(fill=tk.BOTH, expand=True)
        
        self.info_frame = ttk.Frame(self.result_frame)
        self.info_frame.pack(fill=tk.X, pady=10)
        
        # 信息标签
        self.info_text = tk.Text(self.info_frame, height=5, width=70)
        self.info_text.pack(fill=tk.BOTH, expand=True)
        self.info_text.config(state=tk.DISABLED)
        
        # 图表区初始占位
        self.fig = plt.figure(figsize=(8, 6), dpi=100)
        self.canvas = FigureCanvasTkAgg(self.fig, self.canvas_frame)
        self.canvas.get_tk_widget().pack(fill=tk.BOTH, expand=True)
        
        # 添加Matplotlib导航工具栏
        self.toolbar = NavigationToolbar2Tk(self.canvas, self.canvas_frame)
        self.toolbar.update()
        
        # 存储当前解决方案
        self.current_solver = None
        
        # 显示初始消息
        self.update_info("请输入皇后数量N，然后点击'开始求解'按钮。\n对于大规模棋盘(N>200)，可以使用局部视图功能查看细节。\n使用鼠标滚轮可以缩放，按住鼠标左键可以拖动棋盘。")
    
    def update_info(self, message):
        """更新信息文本框"""
        self.info_text.config(state=tk.NORMAL)
        self.info_text.delete(1.0, tk.END)
        self.info_text.insert(tk.END, message)
        self.info_text.config(state=tk.DISABLED)
        self.root.update()
    
    def solve_queens(self):
        """解决N皇后问题"""
        try:
            # 获取并验证N的值
            n = int(self.n_var.get())
            if n <= 3:
                messagebox.showerror("错误", "N必须大于3才有解")
                return
            
            # 禁用开始按钮，防止重复点击
            self.start_button.config(state=tk.DISABLED)
            self.status_var.set("正在求解...")
            self.update_info(f"开始求解{n}皇后问题...\n请稍候...")
            
            # 清除之前的图形
            self.fig.clear()
            
            # 解决N皇后问题
            start_time = time.time()
            solver = NQueensMinConflicts(n)
            success, steps = solver.solve()
            elapsed = time.time() - start_time
            
            if success:
                # 存储当前解决方案
                self.current_solver = solver
                
                # 更新信息
                result_info = (f"找到{n}皇后问题的解决方案!\n"
                              f"用了{steps}步，耗时{elapsed:.4f}秒\n"
                              f"解决方案已验证{'正确' if solver.verify_solution() else '失败'}\n"
                              f"使用鼠标滚轮可以缩放，按住鼠标左键可以拖动棋盘。")
                self.update_info(result_info)
                
                # 可视化棋盘 - 现在支持任何尺寸
                self.visualize_solution(solver)
            else:
                self.update_info(f"未能找到{n}皇后问题的解决方案。\n用了{steps}步，耗时{elapsed:.4f}秒")
            
            self.status_var.set("求解完成")
        
        except ValueError:
            messagebox.showerror("错误", "请输入有效的数字")
            self.status_var.set("输入错误")
        
        except Exception as e:
            messagebox.showerror("错误", f"发生错误: {str(e)}")
            self.status_var.set("发生错误")
        
        finally:
            # 重新启用开始按钮
            self.start_button.config(state=tk.NORMAL)
    
    def update_view(self):
        """更新局部视图范围"""
        if self.current_solver:
            self.visualize_solution(self.current_solver)
    
    def reset_view(self):
        """重置视图到初始状态"""
        if self.current_solver:
            # 重置视图区域设置
            n = self.current_solver.n
            self.view_start_var.set("0")
            self.view_size_var.set(str(min(50, n)))
            # 重新显示
            self.visualize_solution(self.current_solver)
    
    def visualize_solution(self, solver):
        """可视化N皇后问题的解决方案"""
        try:
            n = solver.n
            
            # 获取视图范围
            try:
                view_start = int(self.view_start_var.get())
                view_size = int(self.view_size_var.get())
                # 确保视图范围有效
                view_start = max(0, min(view_start, n-1))
                view_size = max(1, min(view_size, n-view_start))
            except ValueError:
                view_start = 0
                view_size = min(50, n)
            
            # 清除之前的图形
            self.fig.clear()
            
            # 为大规模棋盘使用优化的绘图方法
            if n > 500:
                self.visualize_large_board(solver, view_start, view_size)
            else:
                self.visualize_normal_board(solver, view_start, view_size)
            
            # 更新显示
            self.canvas.draw()
            
        except Exception as e:
            messagebox.showerror("可视化错误", f"绘制棋盘时出错: {str(e)}")
    
    def visualize_normal_board(self, solver, view_start, view_size):
        """可视化正常大小的棋盘"""
        n = solver.n
        view_end = min(view_start + view_size, n)
        
        # 创建子图，启用交互式缩放和平移
        ax = self.fig.add_subplot(111)
        
        # 创建棋盘格子
        board = np.zeros((view_size, view_size))
        for col in range(view_start, view_end):
            row = solver.queens[col]
            if row >= view_start and row < view_end:
                # 将皇后位置标记为1
                board[row-view_start, col-view_start] = 1
        
        # 绘制棋盘
        ax.imshow(board, cmap='binary', extent=[view_start, view_end, view_end, view_start])
        
        # 绘制棋盘线
        # 横线
        for i in range(view_start, view_end + 1):
            ax.axhline(y=i, color='black', linewidth=0.5)
        # 竖线
        for i in range(view_start, view_end + 1):
            ax.axvline(x=i, color='black', linewidth=0.5)
        
        # 在棋盘上标记皇后
        for col in range(view_start, view_end):
            row = solver.queens[col]
            if row >= view_start and row < view_end:
                # 使用更明显的标记
                ax.plot(col + 0.5, row + 0.5, 'ro', markersize=max(3, min(10, 50/view_size)), 
                        markerfacecolor='red', markeredgecolor='black')
        
        # 设置标题和轴标签
        if view_size < n:
            ax.set_title(f"{n}皇后问题的解 (显示区域: {view_start}至{view_end-1})")
        else:
            ax.set_title(f"{n}皇后问题的解")
        
        ax.set_xlabel("列")
        ax.set_ylabel("行")
        
        # 设置网格线
        ax.grid(True, color='black', linestyle='-', linewidth=0.5)
        
        # 设置坐标轴刻度
        if view_size <= 50:
            ax.set_xticks(np.arange(view_start, view_end, 1))
            ax.set_yticks(np.arange(view_start, view_end, 1))
        else:
            # 对于大规模棋盘，减少刻度标记
            step = max(1, view_size // 20)
            ax.set_xticks(np.arange(view_start, view_end, step))
            ax.set_yticks(np.arange(view_start, view_end, step))
        
        # 调整刻度标签大小
        ax.tick_params(axis='both', which='major', labelsize=8)
    
    def visualize_large_board(self, solver, view_start, view_size):
        """为超大规模棋盘使用高效的可视化方法"""
        n = solver.n
        view_end = min(view_start + view_size, n)
        
        # 创建子图
        ax = self.fig.add_subplot(111)
        
        # 只绘制皇后位置，不绘制完整棋盘
        visible_queens_x = []
        visible_queens_y = []
        
        for col in range(view_start, view_end):
            row = solver.queens[col]
            if row >= view_start and row < view_end:
                visible_queens_x.append(col)
                visible_queens_y.append(row)
        
        # 设置坐标范围
        ax.set_xlim(view_start, view_end)
        ax.set_ylim(view_end, view_start)  # 反转Y轴，使(0,0)在左上角
        
        # 绘制网格线 - 使用更少的线以提高性能
        step = max(1, view_size // 50)
        
        # 横线
        for i in range(view_start, view_end + 1, step):
            ax.axhline(y=i, color='gray', linewidth=0.5, alpha=0.5)
        
        # 竖线
        for i in range(view_start, view_end + 1, step):
            ax.axvline(x=i, color='gray', linewidth=0.5, alpha=0.5)
        
        # 绘制皇后位置
        ax.scatter(visible_queens_x, visible_queens_y, s=20, c='red', marker='o')
        
        # 设置标题和轴标签
        ax.set_title(f"{n}皇后问题的解 (显示区域: {view_start}至{view_end-1})")
        ax.set_xlabel("列")
        ax.set_ylabel("行")
        
        # 设置刻度
        ax.set_xticks(np.arange(view_start, view_end, max(1, view_size // 10)))
        ax.set_yticks(np.arange(view_start, view_end, max(1, view_size // 10)))

def main():
    root = tk.Tk()
    app = NQueensUI(root)
    root.mainloop()

if __name__ == "__main__":
    main()